{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cat and Mouse II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #memoization #array #math #dynamic-programming #game-theory #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #记忆化搜索 #数组 #数学 #动态规划 #博弈 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canMouseWin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #猫和老鼠 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。</p>\n",
    "\n",
    "<p>它们所处的环境设定是一个 <code>rows x cols</code> 的方格 <code>grid</code> ，其中每个格子可能是一堵墙、一块地板、一位玩家（猫或者老鼠）或者食物。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>玩家由字符 <code>'C'</code> （代表猫）和 <code>'M'</code> （代表老鼠）表示。</li>\n",
    "\t<li>地板由字符 <code>'.'</code> 表示，玩家可以通过这个格子。</li>\n",
    "\t<li>墙用字符 <code>'#'</code> 表示，玩家不能通过这个格子。</li>\n",
    "\t<li>食物用字符 <code>'F'</code> 表示，玩家可以通过这个格子。</li>\n",
    "\t<li>字符 <code>'C'</code> ， <code>'M'</code> 和 <code>'F'</code> 在 <code>grid</code> 中都只会出现一次。</li>\n",
    "</ul>\n",
    "\n",
    "<p>猫和老鼠按照如下规则移动：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>老鼠 <strong>先移动</strong> ，然后两名玩家轮流移动。</li>\n",
    "\t<li>每一次操作时，猫和老鼠可以跳到上下左右四个方向之一的格子，他们不能跳过墙也不能跳出 <code>grid</code> 。</li>\n",
    "\t<li><code>catJump</code> 和 <code>mouseJump</code> 是猫和老鼠分别跳一次能到达的最远距离，它们也可以跳小于最大距离的长度。</li>\n",
    "\t<li>它们可以停留在原地。</li>\n",
    "\t<li>老鼠可以跳跃过猫的位置。</li>\n",
    "</ul>\n",
    "\n",
    "<p>游戏有 4 种方式会结束：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果猫跟老鼠处在相同的位置，那么猫获胜。</li>\n",
    "\t<li>如果猫先到达食物，那么猫获胜。</li>\n",
    "\t<li>如果老鼠先到达食物，那么老鼠获胜。</li>\n",
    "\t<li>如果老鼠不能在 1000 次操作以内到达食物，那么猫获胜。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你 <code>rows x cols</code> 的矩阵 <code>grid</code> 和两个整数 <code>catJump</code> 和 <code>mouseJump</code> ，双方都采取最优策略，如果老鼠获胜，那么请你返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/17/sample_111_1955.png\" style=\"width: 580px; height: 239px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [\"####F\",\"#C...\",\"M....\"], catJump = 1, mouseJump = 2\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>猫无法抓到老鼠，也没法比老鼠先到达食物。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/17/sample_2_1955.png\" style=\"width: 580px; height: 175px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [\"M.C...F\"], catJump = 1, mouseJump = 4\n",
    "<b>输出：</b>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [\"M.C...F\"], catJump = 1, mouseJump = 3\n",
    "<b>输出：</b>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [\"C...#\",\"...#F\",\"....#\",\"M....\"], catJump = 2, mouseJump = 5\n",
    "<b>输出：</b>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [\".M...\",\"..#..\",\"#..#.\",\"C#.#.\",\"...#F\"], catJump = 3, mouseJump = 1\n",
    "<b>输出：</b>true\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>rows == grid.length</code></li>\n",
    "\t<li><code>cols = grid[i].length</code></li>\n",
    "\t<li><code>1 <= rows, cols <= 8</code></li>\n",
    "\t<li><code>grid[i][j]</code> 只包含字符 <code>'C'</code> ，<code>'M'</code> ，<code>'F'</code> ，<code>'.'</code> 和 <code>'#'</code> 。</li>\n",
    "\t<li><code>grid</code> 中只包含一个 <code>'C'</code> ，<code>'M'</code> 和 <code>'F'</code> 。</li>\n",
    "\t<li><code>1 <= catJump, mouseJump <= 8</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cat-and-mouse-ii](https://leetcode.cn/problems/cat-and-mouse-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cat-and-mouse-ii](https://leetcode.cn/problems/cat-and-mouse-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"####F\",\"#C...\",\"M....\"]\\n1\\n2', '[\"M.C...F\"]\\n1\\n4', '[\"M.C...F\"]\\n1\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# mouse = 0\r\n",
    "# cat = 1\r\n",
    "# define (mi, mj, ci, cj, player, cnt) as the current status\r\n",
    "# initial known states are:\r\n",
    "# f(i, j, i, j, 0, 0) = 1\r\n",
    "# f(Fi, Fj, i, j, 1, 0) = 0\r\n",
    "# f(i, j, Fi, Fj, 0, 0) = 1\r\n",
    "# next state for (mi, mj, ci, cj, 0, cnt) are\r\n",
    "# (mi, mj, ci + a, cj + b, 1, cnt + 1), for 0 <= a, b <= catJump\r\n",
    "# next state for (mi, mj, ci, cj, 1, cnt) are\r\n",
    "# (mi + a, mj + b, ci, cj, 0, cnt + 1), for 0 <= a, b <= mouseJump\r\n",
    "# if f(state) != player, f(next state) = f(state), i.e. player of next state win\r\n",
    "# otherwise if all previous state of a next state having player, f(next state) = f(state), i.e player of next state lose\r\n",
    "# search for f(Mi, Mj, Ci, Cj, 0, <1000)\r\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\r\n",
    "        m = len(grid)\r\n",
    "        n = len(grid[0])\r\n",
    "        mouse = 0\r\n",
    "        cat = 1\r\n",
    "        states: dict[int, int] = dict()\r\n",
    "        prev_cnt: dict[int, int] = dict()\r\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\r\n",
    "\r\n",
    "        def next_state(st: int) -> Generator[int, any, None]:\r\n",
    "            # not move\r\n",
    "            if st ^ 1 not in states: yield(st ^ 1)\r\n",
    "            player = (st & 1) ^ 1\r\n",
    "            cj = (st >> 1) & 7\r\n",
    "            ci = (st >> 4) & 7\r\n",
    "            mj = (st >> 7) & 7\r\n",
    "            mi = (st >> 10) & 7\r\n",
    "            act = [True] * 4\r\n",
    "\r\n",
    "            for x in range(1, (mouseJump if player == mouse else catJump) + 1):\r\n",
    "                for d in range(4):\r\n",
    "                    if not act[d]: continue\r\n",
    "                    a, b = dirs[d]\r\n",
    "                    posi = (mi if player == mouse else ci) + x * a\r\n",
    "                    posj = (mj if player == mouse else cj) + x * b\r\n",
    "                    if posi < 0 or posi == m or posj < 0 or posj == n or grid[posi][posj] == \"#\":\r\n",
    "                        act[d] = False\r\n",
    "                        continue\r\n",
    "                    if grid[posi][posj] == \"#\" or (posi == (ci if player == mouse else mi) and posj == (cj if player == mouse else mj)):\r\n",
    "                        continue\r\n",
    "                    nxt = player\r\n",
    "                    if player == mouse:\r\n",
    "                        nxt |= (posi << 10) | (posj << 7) | (ci << 4) | (cj << 1)\r\n",
    "                    else:\r\n",
    "                        nxt |= (mi << 10) | (mj << 7) | (posi << 4) | (posj << 1)\r\n",
    "                    if nxt not in states:\r\n",
    "                        yield nxt\r\n",
    "\r\n",
    "        def get_prev(st: int) -> None:\r\n",
    "            prev_cnt[st] = 1\r\n",
    "            player = st & 1\r\n",
    "            cj = (st >> 1) & 7\r\n",
    "            ci = (st >> 4) & 7\r\n",
    "            mj = (st >> 7) & 7\r\n",
    "            mi = (st >> 10) & 7\r\n",
    "            act = [True] * 4\r\n",
    "\r\n",
    "            for x in range(1, (mouseJump if player == mouse else catJump) + 1):\r\n",
    "                for d in range(4):\r\n",
    "                    if not act[d]: continue\r\n",
    "                    a, b = dirs[d]\r\n",
    "                    posi = (mi if player == mouse else ci) + x * a\r\n",
    "                    posj = (mj if player == mouse else cj) + x * b\r\n",
    "                    if posi < 0 or posi == m or posj < 0 or posj == n or grid[posi][posj] == \"#\":\r\n",
    "                        act[d] = False\r\n",
    "                        continue\r\n",
    "                    if grid[posi][posj] == \"#\": continue\r\n",
    "                    prev_cnt[st] += 1\r\n",
    "\r\n",
    "        food = 0\r\n",
    "        target = 0\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] == \"F\":\r\n",
    "                    food = (i << 3) | j\r\n",
    "                elif grid[i][j] == \"C\":\r\n",
    "                    target |= (i << 4) | (j << 1)\r\n",
    "                elif grid[i][j] == \"M\":\r\n",
    "                    target |= (i << 10) | (j << 7)\r\n",
    "        \r\n",
    "        q: deque[tuple[int, int]] = deque()\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] == \"F\" or grid[i][j] == \"#\": continue\r\n",
    "                pos = (i << 3) | j\r\n",
    "                states[(pos << 7) | (pos << 1)] = cat \r\n",
    "                q.append(((pos << 7) | (pos << 1), 0))\r\n",
    "                states[(food << 7) | (pos << 1) | cat] = mouse\r\n",
    "                q.append(((food << 7) | (pos << 1) | cat, 0))\r\n",
    "                states[(pos << 7) | (food << 1)] = cat\r\n",
    "                q.append(((pos << 7) | (food << 1), 0))\r\n",
    "        \r\n",
    "        while q:\r\n",
    "            st, cnt = q.popleft()\r\n",
    "            cnt += 1\r\n",
    "            if cnt == 1000: continue\r\n",
    "            for nxt_st in next_state(st):\r\n",
    "                if st & 1 != states[st]:\r\n",
    "                    if nxt_st == target:\r\n",
    "                        return states[st] == mouse\r\n",
    "                    states[nxt_st] = states[st]\r\n",
    "                    q.append((nxt_st, cnt))\r\n",
    "                else:\r\n",
    "                    if nxt_st not in prev_cnt: get_prev(nxt_st)\r\n",
    "                    prev_cnt[nxt_st] -= 1\r\n",
    "                    if prev_cnt[nxt_st] == 0:\r\n",
    "                        if nxt_st == target:\r\n",
    "                            return states[st] == mouse\r\n",
    "                        states[nxt_st] = states[st]\r\n",
    "                        q.append((nxt_st, cnt))\r\n",
    "        \r\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "UNKNOWN = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "MAX_MOVES = 1000\n",
    "DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "\n",
    "        def getPos(row: int, col: int) -> int:\n",
    "            return row * cols + col\n",
    "\n",
    "        startMouse = startCat = food = 0\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, ch in enumerate(row):\n",
    "                if ch == 'M':\n",
    "                    startMouse = getPos(i, j)\n",
    "                elif ch == 'C':\n",
    "                    startCat = getPos(i, j)\n",
    "                elif ch == 'F':\n",
    "                    food = getPos(i, j)\n",
    "\n",
    "        # 计算每个状态的度\n",
    "        total = rows * cols\n",
    "        degrees = [[[0, 0] for _ in range(total)] for _ in range(total)]\n",
    "        for mouse in range(total):\n",
    "            mouseRow, mouseCol = divmod(mouse, cols)\n",
    "            if grid[mouseRow][mouseCol] == '#':\n",
    "                continue\n",
    "            for cat in range(total):\n",
    "                catRow, catCol = divmod(cat, cols)\n",
    "                if grid[catRow][catCol] == '#':\n",
    "                    continue\n",
    "                degrees[mouse][cat][MOUSE_TURN] += 1\n",
    "                degrees[mouse][cat][CAT_TURN] += 1\n",
    "                for dx, dy in DIRS:\n",
    "                    row, col, jump = mouseRow + dx, mouseCol + dy, 1\n",
    "                    while 0 <= row < rows and 0 <= col < cols and grid[row][col] != '#' and jump <= mouseJump:\n",
    "                        nextMouse = getPos(row, col)\n",
    "                        nextCat = getPos(catRow, catCol)\n",
    "                        degrees[nextMouse][nextCat][MOUSE_TURN] += 1\n",
    "                        row += dx\n",
    "                        col += dy\n",
    "                        jump += 1\n",
    "                    row, col, jump = catRow + dx, catCol + dy, 1\n",
    "                    while 0 <= row < rows and 0 <= col < cols and grid[row][col] != '#' and jump <= catJump:\n",
    "                        nextMouse = getPos(mouseRow, mouseCol)\n",
    "                        nextCat = getPos(row, col)\n",
    "                        degrees[nextMouse][nextCat][CAT_TURN] += 1\n",
    "                        row += dx\n",
    "                        col += dy\n",
    "                        jump += 1\n",
    "\n",
    "        results = [[[[0, 0], [0, 0]] for _ in range(total)] for _ in range(total)]\n",
    "        q = deque()\n",
    "\n",
    "        # 猫和老鼠在同一个单元格，猫获胜\n",
    "        for pos in range(total):\n",
    "            row, col = divmod(pos, cols)\n",
    "            if grid[row][col] == '#':\n",
    "                continue\n",
    "            results[pos][pos][MOUSE_TURN][0] = CAT_WIN\n",
    "            results[pos][pos][MOUSE_TURN][1] = 0\n",
    "            results[pos][pos][CAT_TURN][0] = CAT_WIN\n",
    "            results[pos][pos][CAT_TURN][1] = 0\n",
    "            q.append((pos, pos, MOUSE_TURN))\n",
    "            q.append((pos, pos, CAT_TURN))\n",
    "\n",
    "        # 猫和食物在同一个单元格，猫获胜\n",
    "        for mouse in range(total):\n",
    "            mouseRow, mouseCol = divmod(mouse, cols)\n",
    "            if grid[mouseRow][mouseCol] == '#' or mouse == food:\n",
    "                continue\n",
    "            results[mouse][food][MOUSE_TURN][0] = CAT_WIN\n",
    "            results[mouse][food][MOUSE_TURN][1] = 0\n",
    "            results[mouse][food][CAT_TURN][0] = CAT_WIN\n",
    "            results[mouse][food][CAT_TURN][1] = 0\n",
    "            q.append((mouse, food, MOUSE_TURN))\n",
    "            q.append((mouse, food, CAT_TURN))\n",
    "\n",
    "        # 老鼠和食物在同一个单元格且猫和食物不在同一个单元格，老鼠获胜\n",
    "        for cat in range(total):\n",
    "            catRow, catCol = divmod(cat, cols)\n",
    "            if grid[catRow][catCol] == '#' or cat == food:\n",
    "                continue\n",
    "            results[food][cat][MOUSE_TURN][0] = MOUSE_WIN\n",
    "            results[food][cat][MOUSE_TURN][1] = 0\n",
    "            results[food][cat][CAT_TURN][0] = MOUSE_WIN\n",
    "            results[food][cat][CAT_TURN][1] = 0\n",
    "            q.append((food, cat, MOUSE_TURN))\n",
    "            q.append((food, cat, CAT_TURN))\n",
    "\n",
    "        def getPrevStates(mouse: int, cat: int, turn: int) -> List[Tuple[int, int, int]]:\n",
    "            mouseRow, mouseCol = divmod(mouse, cols)\n",
    "            catRow, catCol = divmod(cat, cols)\n",
    "            prevTurn = CAT_TURN if turn == MOUSE_TURN else MOUSE_TURN\n",
    "            maxJump = mouseJump if prevTurn == MOUSE_TURN else catJump\n",
    "            startRow = mouseRow if prevTurn == MOUSE_TURN else catRow\n",
    "            startCol = mouseCol if prevTurn == MOUSE_TURN else catCol\n",
    "            prevStates = [(mouse, cat, prevTurn)]\n",
    "            for dx, dy in DIRS:\n",
    "                i, j, jump = startRow + dx, startCol + dy, 1\n",
    "                while 0 <= i < rows and 0 <= j < cols and grid[i][j] != '#' and jump <= maxJump:\n",
    "                    prevMouseRow = i if prevTurn == MOUSE_TURN else mouseRow\n",
    "                    prevMouseCol = j if prevTurn == MOUSE_TURN else mouseCol\n",
    "                    prevCatRow = catRow if prevTurn == MOUSE_TURN else i\n",
    "                    prevCatCol = catCol if prevTurn == MOUSE_TURN else j\n",
    "                    prevMouse = getPos(prevMouseRow, prevMouseCol)\n",
    "                    prevCat = getPos(prevCatRow, prevCatCol)\n",
    "                    prevStates.append((prevMouse, prevCat, prevTurn))\n",
    "                    i += dx\n",
    "                    j += dy\n",
    "                    jump += 1\n",
    "            return prevStates\n",
    "\n",
    "        # 拓扑排序\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn][0]\n",
    "            moves = results[mouse][cat][turn][1]\n",
    "            for prevMouse, prevCat, prevTurn in getPrevStates(mouse, cat, turn):\n",
    "                if results[prevMouse][prevCat][prevTurn][0] == UNKNOWN:\n",
    "                    if result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN:\n",
    "                        results[prevMouse][prevCat][prevTurn][0] = result\n",
    "                        results[prevMouse][prevCat][prevTurn][1] = moves + 1\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            loseResult = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            results[prevMouse][prevCat][prevTurn][0] = loseResult\n",
    "                            results[prevMouse][prevCat][prevTurn][1] = moves + 1\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[startMouse][startCat][MOUSE_TURN][0] == MOUSE_WIN and results[startMouse][startCat][MOUSE_TURN][1] <= MAX_MOVES"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "UNKNOWN = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "MAX_MOVES = 1000\n",
    "DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "\n",
    "        def getPos(row: int, col: int) -> int:\n",
    "            return row * cols + col\n",
    "\n",
    "        startMouse = startCat = food = 0\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, ch in enumerate(row):\n",
    "                if ch == 'M':\n",
    "                    startMouse = getPos(i, j)\n",
    "                elif ch == 'C':\n",
    "                    startCat = getPos(i, j)\n",
    "                elif ch == 'F':\n",
    "                    food = getPos(i, j)\n",
    "\n",
    "        # 计算每个状态的度\n",
    "        total = rows * cols\n",
    "        degrees = [[[0, 0] for _ in range(total)] for _ in range(total)]\n",
    "        for mouse in range(total):\n",
    "            mouseRow, mouseCol = divmod(mouse, cols)\n",
    "            if grid[mouseRow][mouseCol] == '#':\n",
    "                continue\n",
    "            for cat in range(total):\n",
    "                catRow, catCol = divmod(cat, cols)\n",
    "                if grid[catRow][catCol] == '#':\n",
    "                    continue\n",
    "                degrees[mouse][cat][MOUSE_TURN] += 1\n",
    "                degrees[mouse][cat][CAT_TURN] += 1\n",
    "                for dx, dy in DIRS:\n",
    "                    row, col, jump = mouseRow + dx, mouseCol + dy, 1\n",
    "                    while 0 <= row < rows and 0 <= col < cols and grid[row][col] != '#' and jump <= mouseJump:\n",
    "                        nextMouse = getPos(row, col)\n",
    "                        nextCat = getPos(catRow, catCol)\n",
    "                        degrees[nextMouse][nextCat][MOUSE_TURN] += 1\n",
    "                        row += dx\n",
    "                        col += dy\n",
    "                        jump += 1\n",
    "                    row, col, jump = catRow + dx, catCol + dy, 1\n",
    "                    while 0 <= row < rows and 0 <= col < cols and grid[row][col] != '#' and jump <= catJump:\n",
    "                        nextMouse = getPos(mouseRow, mouseCol)\n",
    "                        nextCat = getPos(row, col)\n",
    "                        degrees[nextMouse][nextCat][CAT_TURN] += 1\n",
    "                        row += dx\n",
    "                        col += dy\n",
    "                        jump += 1\n",
    "\n",
    "        results = [[[[0, 0], [0, 0]] for _ in range(total)] for _ in range(total)]\n",
    "        q = deque()\n",
    "\n",
    "        # 猫和老鼠在同一个单元格，猫获胜\n",
    "        for pos in range(total):\n",
    "            row, col = divmod(pos, cols)\n",
    "            if grid[row][col] == '#':\n",
    "                continue\n",
    "            results[pos][pos][MOUSE_TURN][0] = CAT_WIN\n",
    "            results[pos][pos][MOUSE_TURN][1] = 0\n",
    "            results[pos][pos][CAT_TURN][0] = CAT_WIN\n",
    "            results[pos][pos][CAT_TURN][1] = 0\n",
    "            q.append((pos, pos, MOUSE_TURN))\n",
    "            q.append((pos, pos, CAT_TURN))\n",
    "\n",
    "        # 猫和食物在同一个单元格，猫获胜\n",
    "        for mouse in range(total):\n",
    "            mouseRow, mouseCol = divmod(mouse, cols)\n",
    "            if grid[mouseRow][mouseCol] == '#' or mouse == food:\n",
    "                continue\n",
    "            results[mouse][food][MOUSE_TURN][0] = CAT_WIN\n",
    "            results[mouse][food][MOUSE_TURN][1] = 0\n",
    "            results[mouse][food][CAT_TURN][0] = CAT_WIN\n",
    "            results[mouse][food][CAT_TURN][1] = 0\n",
    "            q.append((mouse, food, MOUSE_TURN))\n",
    "            q.append((mouse, food, CAT_TURN))\n",
    "\n",
    "        # 老鼠和食物在同一个单元格且猫和食物不在同一个单元格，老鼠获胜\n",
    "        for cat in range(total):\n",
    "            catRow, catCol = divmod(cat, cols)\n",
    "            if grid[catRow][catCol] == '#' or cat == food:\n",
    "                continue\n",
    "            results[food][cat][MOUSE_TURN][0] = MOUSE_WIN\n",
    "            results[food][cat][MOUSE_TURN][1] = 0\n",
    "            results[food][cat][CAT_TURN][0] = MOUSE_WIN\n",
    "            results[food][cat][CAT_TURN][1] = 0\n",
    "            q.append((food, cat, MOUSE_TURN))\n",
    "            q.append((food, cat, CAT_TURN))\n",
    "\n",
    "        def getPrevStates(mouse: int, cat: int, turn: int) -> List[Tuple[int, int, int]]:\n",
    "            mouseRow, mouseCol = divmod(mouse, cols)\n",
    "            catRow, catCol = divmod(cat, cols)\n",
    "            prevTurn = CAT_TURN if turn == MOUSE_TURN else MOUSE_TURN\n",
    "            maxJump = mouseJump if prevTurn == MOUSE_TURN else catJump\n",
    "            startRow = mouseRow if prevTurn == MOUSE_TURN else catRow\n",
    "            startCol = mouseCol if prevTurn == MOUSE_TURN else catCol\n",
    "            prevStates = [(mouse, cat, prevTurn)]\n",
    "            for dx, dy in DIRS:\n",
    "                i, j, jump = startRow + dx, startCol + dy, 1\n",
    "                while 0 <= i < rows and 0 <= j < cols and grid[i][j] != '#' and jump <= maxJump:\n",
    "                    prevMouseRow = i if prevTurn == MOUSE_TURN else mouseRow\n",
    "                    prevMouseCol = j if prevTurn == MOUSE_TURN else mouseCol\n",
    "                    prevCatRow = catRow if prevTurn == MOUSE_TURN else i\n",
    "                    prevCatCol = catCol if prevTurn == MOUSE_TURN else j\n",
    "                    prevMouse = getPos(prevMouseRow, prevMouseCol)\n",
    "                    prevCat = getPos(prevCatRow, prevCatCol)\n",
    "                    prevStates.append((prevMouse, prevCat, prevTurn))\n",
    "                    i += dx\n",
    "                    j += dy\n",
    "                    jump += 1\n",
    "            return prevStates\n",
    "\n",
    "        # 拓扑排序\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn][0]\n",
    "            moves = results[mouse][cat][turn][1]\n",
    "            for prevMouse, prevCat, prevTurn in getPrevStates(mouse, cat, turn):\n",
    "                if results[prevMouse][prevCat][prevTurn][0] == UNKNOWN:\n",
    "                    if result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN:\n",
    "                        results[prevMouse][prevCat][prevTurn][0] = result\n",
    "                        results[prevMouse][prevCat][prevTurn][1] = moves + 1\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            loseResult = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            results[prevMouse][prevCat][prevTurn][0] = loseResult\n",
    "                            results[prevMouse][prevCat][prevTurn][1] = moves + 1\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[startMouse][startCat][MOUSE_TURN][0] == MOUSE_WIN and results[startMouse][startCat][MOUSE_TURN][1] <= MAX_MOVES"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "direction = [-1, 0, 1, 0, -1]\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'C':\n",
    "                    cx, cy = i, j\n",
    "                elif grid[i][j] == 'M':\n",
    "                    mx, my = i, j\n",
    "                elif grid[i][j] == 'F':\n",
    "                    fx, fy = i, j\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x1, y1, x2, y2, f, step):\n",
    "            if (x1, y1) == (fx, fy) or (x1, y1) == (x2, y2) or step >= 40:\n",
    "                return f == 1\n",
    "            if (x2, y2) == (fx, fy):\n",
    "                return f == 0\n",
    "            \n",
    "            if f == 0:\n",
    "                for dx, dy in pairwise(direction):\n",
    "                    for d in range(mouseJump + 1):\n",
    "                        a, b = x2 + dx * d, y2 + dy * d\n",
    "                        if 0 <= a < m and 0 <= b < n and grid[a][b] != '#':\n",
    "                            t = dfs(x1, y1, a, b, 1, step)\n",
    "                            if not t:\n",
    "                                return True\n",
    "                        else:\n",
    "                            break\n",
    "            else:\n",
    "                for dx, dy in pairwise(direction):\n",
    "                    for d in range(catJump + 1):\n",
    "                        a, b = x1 + dx * d, y1 + dy * d\n",
    "                        if 0 <= a < m and 0 <= b < n and grid[a][b] != '#':\n",
    "                            t = dfs(a, b, x2, y2, 0, step + 1)\n",
    "                            if not t:\n",
    "                                return True\n",
    "                        else:\n",
    "                            break\n",
    "            \n",
    "            return False\n",
    "\n",
    "        ans = dfs(cx, cy, mx, my, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        DRAW, MOUSE, CAT = 'DRAW', 'MOUSE', 'CAT'\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mousePos, catPos, foodPos = None, None, None\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'M':\n",
    "                    mousePos = (i, j)\n",
    "                elif grid[i][j] == 'C':\n",
    "                    catPos = (i, j)\n",
    "                elif grid[i][j] == 'F':\n",
    "                    foodPos = (i, j)\n",
    "        memo = {}\n",
    "        def helper(mouse: Tuple[int, int], cat: Tuple[int, int], turn: int) -> str:\n",
    "            if mouse == cat or cat == foodPos or turn == 2 * m * n:\n",
    "                return CAT\n",
    "            if mouse == foodPos:\n",
    "                return MOUSE\n",
    "            if (mouse, cat, turn) in memo:\n",
    "                return memo[(mouse, cat, turn)]\n",
    "            mx, my = mouse\n",
    "            cx, cy = cat\n",
    "            if turn % 2 == 0:\n",
    "                for dx, dy in directions:\n",
    "                    for step in range(mouseJump + 1):\n",
    "                        nx, ny = mx + dx * step, my + dy * step\n",
    "                        if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] == '#':\n",
    "                            break\n",
    "                        if helper((nx, ny), cat, turn + 1) == MOUSE:\n",
    "                            memo[(mouse, cat, turn)] = MOUSE\n",
    "                            return MOUSE\n",
    "                memo[(mouse, cat, turn)] = CAT\n",
    "            else:\n",
    "                for dx, dy in directions:\n",
    "                    for step in range(catJump + 1):\n",
    "                        nx, ny = cx + dx * step, cy + dy * step\n",
    "                        if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] == '#':\n",
    "                            break\n",
    "                        if helper(mouse, (nx, ny), turn + 1) == CAT:\n",
    "                            memo[(mouse, cat, turn)] = CAT\n",
    "                            return CAT\n",
    "                memo[(mouse, cat, turn)] = MOUSE\n",
    "            return memo[(mouse, cat, turn)]\n",
    "        return helper(mousePos, catPos, 0) == MOUSE\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        mm, nn = len(grid), len(grid[0])\n",
    "        for x in range(mm):\n",
    "            for y in range(nn):\n",
    "                match grid[x][y]:\n",
    "                    case 'C':\n",
    "                        cat = x, y\n",
    "                    case 'F':\n",
    "                        food = x, y\n",
    "                    case 'M':\n",
    "                        mouse = x, y\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(m, c, i):\n",
    "            \"\"\"\n",
    "            极大极小博弈，\n",
    "            老鼠尽量找自己获胜的，其次接受平局\n",
    "            猫尽量找自己获胜的，其次接受平局\n",
    "\n",
    "            :param m: 老鼠的位置\n",
    "            :param c: 猫的位置\n",
    "            :param i: 回合\n",
    "            \"\"\"\n",
    "            if m == c or c == food or i > 128:\n",
    "                return False\n",
    "            if m == food:\n",
    "                return True\n",
    "            is_cat = False\n",
    "            # 猫回合\n",
    "            if i % 2:\n",
    "                pos, jump = c, catJump\n",
    "                is_cat = True\n",
    "            else:\n",
    "                pos, jump = m, mouseJump\n",
    "            for dx, dy in DIRS:\n",
    "                for jp in range(jump + 1):\n",
    "                    nx, ny = pos[0] + dx * jp, pos[1] + dy * jp\n",
    "                    if nx < 0 or ny < 0 or nx >= mm or ny >= nn or grid[nx][ny] == '#':\n",
    "                        break\n",
    "                    if not is_cat and dfs((nx, ny), c, i + 1):\n",
    "                        return True\n",
    "                    elif is_cat and not dfs(m, (nx, ny), i + 1):\n",
    "                        return False\n",
    "            return is_cat\n",
    "        \n",
    "        return dfs(mouse, cat, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        mm, nn = len(grid), len(grid[0])\n",
    "        for x in range(mm):\n",
    "            for y in range(nn):\n",
    "                match grid[x][y]:\n",
    "                    case 'C':\n",
    "                        cat = x, y\n",
    "                    case 'F':\n",
    "                        food = x, y\n",
    "                    case 'M':\n",
    "                        mouse = x, y\n",
    "        @cache\n",
    "        def dfs(m, c, i):\n",
    "            if m == c or c == food or i > 128:\n",
    "                return False\n",
    "            if m == food:\n",
    "                return True\n",
    "            is_cat = False\n",
    "            # 猫回合\n",
    "            if i % 2:\n",
    "                pos, jump = c, catJump\n",
    "                is_cat = True\n",
    "            else:\n",
    "                pos, jump = m, mouseJump\n",
    "            for dx, dy in DIRS:\n",
    "                for jp in range(jump + 1):\n",
    "                    nx, ny = pos[0] + dx * jp, pos[1] + dy * jp\n",
    "                    if nx < 0 or ny < 0 or nx >= mm or ny >= nn or grid[nx][ny] == '#':\n",
    "                        break\n",
    "                    if not is_cat and dfs((nx, ny), c, i + 1):\n",
    "                        return True\n",
    "                    elif is_cat and not dfs(m, (nx, ny), i + 1):\n",
    "                        return False\n",
    "            return is_cat\n",
    "        return dfs(mouse, cat, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        mm, nn = len(grid), len(grid[0])\n",
    "        for x in range(mm):\n",
    "            for y in range(nn):\n",
    "                match grid[x][y]:\n",
    "                    case 'C':\n",
    "                        cat = x, y\n",
    "                    case 'F':\n",
    "                        food = x, y\n",
    "                    case 'M':\n",
    "                        mouse = x, y\n",
    "        @lru_cache(None)\n",
    "        def dfs(m, c, i):\n",
    "            if m == c or c == food or i > 128:\n",
    "                return False\n",
    "            if m == food:\n",
    "                return True\n",
    "            is_cat = False\n",
    "            # 猫回合\n",
    "            if i % 2:\n",
    "                pos, jump = c, catJump\n",
    "                is_cat = True\n",
    "            else:\n",
    "                pos, jump = m, mouseJump\n",
    "            for dx, dy in DIRS:\n",
    "                for jp in range(jump + 1):\n",
    "                    nx, ny = pos[0] + dx * jp, pos[1] + dy * jp\n",
    "                    if nx < 0 or ny < 0 or nx >= mm or ny >= nn or grid[nx][ny] == '#':\n",
    "                        break\n",
    "                    if not is_cat and dfs((nx, ny), c, i + 1):\n",
    "                        return True\n",
    "                    elif is_cat and not dfs(m, (nx, ny), i + 1):\n",
    "                        return False\n",
    "            return is_cat\n",
    "        return dfs(mouse, cat, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def moves(i, j, max_jump):\n",
    "            for jump in range(1, max_jump + 1):\n",
    "                if i + jump < m and grid[i + jump][j] != '#':\n",
    "                    yield i + jump, j\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            for jump in range(1, max_jump + 1):\n",
    "                if i - jump >= 0 and grid[i - jump][j] != '#':\n",
    "                    yield i - jump, j\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            for jump in range(1, max_jump + 1):\n",
    "                if j + jump < n and grid[i][j + jump] != '#':\n",
    "                    yield i, j + jump\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            for jump in range(1, max_jump + 1):\n",
    "                if j - jump >= 0 and grid[i][j - jump] != '#':\n",
    "                    yield i, j - jump\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            yield i, j\n",
    "\n",
    "        @cache\n",
    "        def dp(t, a, b, c, d):\n",
    "            if a == c and b == d:\n",
    "                return False\n",
    "\n",
    "            if grid[c][d] == 'F':\n",
    "                return False\n",
    "\n",
    "            if t >= m * n * 2:\n",
    "                return False\n",
    "\n",
    "            if grid[a][b] == 'F':\n",
    "                return True\n",
    "            \n",
    "            if t % 2 == 0:\n",
    "                for i, j in moves(a, b, mouseJump):\n",
    "                    if dp(t + 1, i, j, c, d):\n",
    "                        return True\n",
    "\n",
    "                return False\n",
    "\n",
    "            else:\n",
    "                for i, j in moves(c, d, catJump):\n",
    "                    if not dp(t + 1, a, b, i, j):\n",
    "                        return False\n",
    "\n",
    "                return True\n",
    "\n",
    "        a = b = c = d = -1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'C':\n",
    "                    c, d = i, j\n",
    "                elif grid[i][j] == 'M':\n",
    "                    a, b = i, j\n",
    "\n",
    "        return dp(0, a, b, c, d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def moves(i, j, max_jump):\n",
    "            for jump in range(1, max_jump + 1):\n",
    "                if i + jump < m and grid[i + jump][j] != '#':\n",
    "                    yield i + jump, j\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            for jump in range(1, max_jump + 1):\n",
    "                if i - jump >= 0 and grid[i - jump][j] != '#':\n",
    "                    yield i - jump, j\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            for jump in range(1, max_jump + 1):\n",
    "                if j + jump < n and grid[i][j + jump] != '#':\n",
    "                    yield i, j + jump\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            for jump in range(1, max_jump + 1):\n",
    "                if j - jump >= 0 and grid[i][j - jump] != '#':\n",
    "                    yield i, j - jump\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            yield i, j\n",
    "\n",
    "        @cache\n",
    "        def dp(t, a, b, c, d):\n",
    "            # print(t, a, b, c, d, grid[a][b] == 'F', grid[c][d] == 'F')\n",
    "            if a == c and b == d:\n",
    "                return False\n",
    "\n",
    "            if grid[c][d] == 'F':\n",
    "                return False\n",
    "\n",
    "            if t >= m * n * 2:\n",
    "                return False\n",
    "\n",
    "            if grid[a][b] == 'F':\n",
    "                return True\n",
    "            \n",
    "            if t % 2 == 0:\n",
    "                for i, j in moves(a, b, mouseJump):\n",
    "                    if dp(t + 1, i, j, c, d):\n",
    "                        return True\n",
    "\n",
    "                return False\n",
    "\n",
    "            else:\n",
    "                for i, j in moves(c, d, catJump):\n",
    "                    if not dp(t + 1, a, b, i, j):\n",
    "                        return False\n",
    "\n",
    "                return True\n",
    "\n",
    "        a = b = c = d = -1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'C':\n",
    "                    c, d = i, j\n",
    "                elif grid[i][j] == 'M':\n",
    "                    a, b = i, j\n",
    "\n",
    "        return dp(0, a, b, c, d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        d=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"F\":\n",
    "                    fx,fy=i,j\n",
    "                elif grid[i][j]==\"C\":\n",
    "                    cx,cy=i,j\n",
    "                elif grid[i][j]==\"M\":\n",
    "                    mx,my=i,j\n",
    "        @cache\n",
    "        def dfs(x,y,a,b,v):\n",
    "            if x==fx and y==fy:\n",
    "                return True\n",
    "            if v>128:\n",
    "                return False\n",
    "            if a==fx and b==fy:\n",
    "                return False\n",
    "            if x==a and y==b:\n",
    "                return False \n",
    "            if v%2==0:#mouse\n",
    "                for xx,yy in d:\n",
    "                    c=0\n",
    "                    xxx,yyy=x,y\n",
    "                    while True:\n",
    "                        xxx+=xx\n",
    "                        yyy+=yy\n",
    "                        c+=1\n",
    "                        if c>mouseJump:\n",
    "                            break\n",
    "                        if xxx>=m or yyy>=n or xxx<0 or yyy<0:\n",
    "                            continue\n",
    "                        if grid[xxx][yyy]==\"#\":\n",
    "                            break\n",
    "                        if dfs(xxx,yyy,a,b,v+1):\n",
    "                            return True\n",
    "                return False\n",
    "            elif v%2==1:#cat\n",
    "                for xx,yy in d:\n",
    "                    c=0\n",
    "                    xxx,yyy=a,b\n",
    "                    while True:\n",
    "                        xxx+=xx\n",
    "                        yyy+=yy\n",
    "                        c+=1\n",
    "                        if c>catJump:\n",
    "                            break\n",
    "                        if xxx>=m or yyy>=n or xxx<0 or yyy<0:\n",
    "                            continue\n",
    "                        if grid[xxx][yyy]==\"#\":\n",
    "                            break\n",
    "                        if not dfs(x,y,xxx,yyy,v+1):\n",
    "                            return False\n",
    "                if not dfs(x,y,a,b,v+1):\n",
    "                    return False\n",
    "                return True\n",
    "        return dfs(mx,my,cx,cy,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        dirs = [0, 1, 0, -1, 0]\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        nFloors = 0\n",
    "        cat = 0  # cat's position\n",
    "        mouse = 0  # mouse's position\n",
    "\n",
    "        def hash(i: int, j: int) -> int:\n",
    "            return i * n + j\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != \"#\":\n",
    "                    nFloors += 1\n",
    "                if grid[i][j] == \"C\":\n",
    "                    cat = hash(i, j)\n",
    "                elif grid[i][j] == \"M\":\n",
    "                    mouse = hash(i, j)\n",
    "\n",
    "        # dp(i, j, k) := True if mouse can win w//\n",
    "        # Cat on (i // 8, i % 8), mouse on (j // 8, j % 8), and turns = k\n",
    "        @functools.lru_cache(None)\n",
    "        def dp(cat: int, mouse: int, turn: int) -> bool:\n",
    "            # We already search whole touchable grid\n",
    "            if turn == nFloors * 2:\n",
    "                return False\n",
    "\n",
    "            if turn % 2 == 0:\n",
    "                # mouse's turn\n",
    "                i = mouse // n\n",
    "                j = mouse % n\n",
    "                for k in range(4):\n",
    "                    for jump in range(mouseJump + 1):\n",
    "                        x = i + dirs[k] * jump\n",
    "                        y = j + dirs[k + 1] * jump\n",
    "                        if x < 0 or x == m or y < 0 or y == n:\n",
    "                            break\n",
    "                        if grid[x][y] == \"#\":\n",
    "                            break\n",
    "                        if grid[x][y] == \"F\":  # Mouse eats the food, so mouse win\n",
    "                            return True\n",
    "                        if dp(cat, hash(x, y), turn + 1):\n",
    "                            return True\n",
    "                # Mouse can't win, so mouse lose\n",
    "                return False\n",
    "            else:\n",
    "                # cat's turn\n",
    "                i = cat // n\n",
    "                j = cat % n\n",
    "                for k in range(4):\n",
    "                    for jump in range(catJump + 1):\n",
    "                        x = i + dirs[k] * jump\n",
    "                        y = j + dirs[k + 1] * jump\n",
    "                        if x < 0 or x == m or y < 0 or y == n:\n",
    "                            break\n",
    "                        if grid[x][y] == \"#\":\n",
    "                            break\n",
    "                        if grid[x][y] == \"F\":  # Cat eats the food, so mouse lose\n",
    "                            return False\n",
    "                        nextCat = hash(x, y)\n",
    "                        if nextCat == mouse:  # Cat catches mouse, so mouse lose\n",
    "                            return False\n",
    "                        if not dp(nextCat, mouse, turn + 1):\n",
    "                            return False\n",
    "                # Cat can't win, so mouse win\n",
    "                return True\n",
    "\n",
    "        return dp(cat, mouse, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:\n",
    "        d=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"F\":\n",
    "                    fx,fy=i,j\n",
    "                elif grid[i][j]==\"C\":\n",
    "                    cx,cy=i,j\n",
    "                elif grid[i][j]==\"M\":\n",
    "                    mx,my=i,j\n",
    "        rem=dict()\n",
    "        def dfs(x,y,a,b,v):\n",
    "            if (x,y,a,b,v) in rem:\n",
    "                return rem[(x,y,a,b,v)]\n",
    "            if x==fx and y==fy:\n",
    "                return True\n",
    "            if v>128:\n",
    "                return False\n",
    "            if a==fx and b==fy:\n",
    "                return False\n",
    "            if x==a and y==b:\n",
    "                return False \n",
    "            if v%2==0:#mouse\n",
    "                for xx,yy in d:\n",
    "                    c=0\n",
    "                    xxx,yyy=x,y\n",
    "                    while True:\n",
    "                        xxx+=xx\n",
    "                        yyy+=yy\n",
    "                        c+=1\n",
    "                        if c>mouseJump:\n",
    "                            break\n",
    "                        if xxx>=m or yyy>=n or xxx<0 or yyy<0:\n",
    "                            continue\n",
    "                        if grid[xxx][yyy]==\"#\":\n",
    "                            break\n",
    "                        if dfs(xxx,yyy,a,b,v+1):\n",
    "                            rem[(x,y,a,b,v)]=True\n",
    "                            return True\n",
    "                rem[(x,y,a,b,v)]=False\n",
    "                return False\n",
    "            elif v%2==1:#cat\n",
    "                for xx,yy in d:\n",
    "                    c=0\n",
    "                    xxx,yyy=a,b\n",
    "                    while True:\n",
    "                        xxx+=xx\n",
    "                        yyy+=yy\n",
    "                        c+=1\n",
    "                        if c>catJump:\n",
    "                            break\n",
    "                        if xxx>=m or yyy>=n or xxx<0 or yyy<0:\n",
    "                            continue\n",
    "                        if grid[xxx][yyy]==\"#\":\n",
    "                            break\n",
    "                        if not dfs(x,y,xxx,yyy,v+1):\n",
    "                            rem[(x,y,a,b,v)]=False\n",
    "                            return False\n",
    "                if not dfs(x,y,a,b,v+1):\n",
    "                    rem[(x,y,a,b,v)]=False\n",
    "                    return False\n",
    "                rem[(x,y,a,b,v)]=True\n",
    "                return True\n",
    "        return dfs(mx,my,cx,cy,0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
